package com.summli.basic.class02;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 双端链表实现队列，栈
 */
public class Code03_DoubleEndsQueueToStackAndQueue {
    /**
     * 栈
     * @param <T>
     */
    public static class MyStack<T>{
        private DoubleEndsQueue<T> queue;

        public MyStack() {
            queue = new DoubleEndsQueue<>();
        }

        public void push(T value){
            queue.addFormHead(value);
        }

        public T pop(){
            return queue.popFromHead();
        }
    }

    /**
     * 队列
     */
    public static class MyQueue<T>{
        private DoubleEndsQueue<T> queue;

        public MyQueue() {
            queue = new DoubleEndsQueue();
        }
        public void push(T value){
            queue.addFormHead(value);
        }
        public T poll(){
            return queue.popFromBottom();
        }
    }
    /**
     * 双端链表结构
     * @param <T>
     */
    public static class Node<T> {
        public T value;
        public Node<T> last;
        public Node<T> next;
        public Node(T data) {
            value = data;
        }
    }
    public static class DoubleEndsQueue<T> {
        public Node<T> head;
        public Node<T> tail;
        /**
         * 添加链表头
         */
        public void addFormHead(T value){
            Node<T> cur = new Node<T>(value);
            if(head == null){
                head = cur;
                tail = cur;
            }else{
                cur.next = head;
                head.last = cur;
                head = cur;
            }
        }
        /**
         * 添加链表尾
         */
        public void addFormBottom(T value){
            Node<T> cur = new Node<>(value);
            if(head == null){
                head = cur;
                tail = cur;
            }else{
                tail.next = cur;
                cur.last = tail;
                tail = cur;
            }
        }
        /**
         * 弹出链表头
         */
        public T popFromHead() {
            if(isEmpty()){
                return null;
            }
            Node<T> result = head;
            if(head == tail){
                head = null;
                tail = null;
            }else{
                head = head.next;
                head.last = null;
                result.next = null;
            }
            return result.value;
        }
        /**
         * 弹出链表尾
         */
        public T popFromBottom() {
            if(isEmpty()){
                return null;
            }
            Node<T> result = tail;
            if(head == tail){
                head = null;
                tail = null;
            }else{
                tail = tail.last;
                tail.next = null;
                result.last = null;
            }
            return result.value;
        }
        /**
         * 判空
         */
        public boolean isEmpty() {
            return head == null;
        }

        //对数器
        public static boolean isEqual(Integer o1, Integer o2) {
            if (o1 == null && o2 != null) {
                return false;
            }
            if (o1 != null && o2 == null) {
                return false;
            }
            if (o1 == null && o2 == null) {
                return true;
            }
            return o1.equals(o2);
        }

        public static void main(String[] args) {
            int oneTestDataNum = 100;
            int value = 10000;
            int testTimes = 100000;
            for (int i = 0; i < testTimes; i++) {
                MyStack<Integer> myStack = new MyStack<>();
                MyQueue<Integer> myQueue = new MyQueue<>();
                Stack<Integer> stack = new Stack<>();
                Queue<Integer> queue = new LinkedList<>();
                for (int j = 0; j < oneTestDataNum; j++) {
                    int nums = (int) (Math.random() * value);
                    if (stack.isEmpty()) {
                        myStack.push(nums);
                        stack.push(nums);
                    } else {
                        if (Math.random() < 0.5) {
                            myStack.push(nums);
                            stack.push(nums);
                        } else {
                            if (!isEqual(myStack.pop(), stack.pop())) {
                                System.out.println("oops!");
                            }
                        }
                    }
                    int numq = (int) (Math.random() * value);
                    if (stack.isEmpty()) {
                        myQueue.push(numq);
                        queue.offer(numq);
                    } else {
                        if (Math.random() < 0.5) {
                            myQueue.push(numq);
                            queue.offer(numq);
                        } else {
                            if (!isEqual(myQueue.poll(), queue.poll())) {
                                System.out.println("oops!");
                            }
                        }
                    }
                }
            }
            System.out.println("finish!");
        }
    }

}
